সার্চিং অ্যালগরিদম (Searching Algorithms)
সার্চিং অ্যালগরিদম হলো একটি প্রক্রিয়া যা নির্দিষ্ট ডেটা স্ট্রাকচারে একটি নির্দিষ্ট মান খুঁজে বের করার জন্য ব্যবহৃত হয়। দুটি জনপ্রিয় সার্চিং অ্যালগরিদম হলো লিনিয়ার সার্চ এবং বাইনারি সার্চ।
১. লিনিয়ার সার্চ (Linear Search)
লিনিয়ার সার্চ হলো একটি সরল অ্যালগরিদম যা একটি তালিকায় প্রতিটি উপাদান এক এক করে পরীক্ষা করে লক্ষ্য মানটি খুঁজে বের করে। এটি সবচেয়ে সহজ এবং মৌলিক সার্চিং পদ্ধতি।
বিশেষত্ব:
- টাইম কমপ্লেক্সিটি: O(n), যেখানে n হলো তালিকার আকার।
- এটি অর্ডারড বা আনঅর্ডারড উভয় ধরনের তালিকায় কাজ করে।
লিনিয়ার সার্চের কাজ করার প্রক্রিয়া:
- প্রথম উপাদান থেকে শুরু করুন।
- প্রতিটি উপাদান লক্ষ্য মানের সাথে তুলনা করুন।
- যদি মানটি পাওয়া যায়, তাহলে ইনডেক্স ফেরত দিন।
- যদি শেষ উপাদান পরীক্ষা করে কোন ফলাফল না পাওয়া যায়, তাহলে "নেই" ফেরত দিন।
উদাহরণ (Python):
def linear_search(arr, target):
for index in range(len(arr)):
if arr[index] == target:
return index # লক্ষ্য মানের ইনডেক্স ফেরত
return -1 # লক্ষ্য মান না পেলে -1 ফেরত
# ব্যবহার উদাহরণ
arr = [4, 2, 3, 5, 1]
target = 3
result = linear_search(arr, target)
print(result) # আউটপুট: 2
২. বাইনারি সার্চ (Binary Search)
বাইনারি সার্চ একটি দ্রুত সার্চিং অ্যালগরিদম যা একটি সাজানো তালিকায় কাজ করে। এটি তালিকার মধ্যবর্তী উপাদানের মানের সাথে লক্ষ্য মানের তুলনা করে, এবং এর ভিত্তিতে সার্চের পরিসীমা অর্ধেক করে দেয়।
বিশেষত্ব:
- টাইম কমপ্লেক্সিটি: O(log n), যেখানে n হলো তালিকার আকার।
- শুধুমাত্র সাজানো তালিকার জন্য কার্যকর।
বাইনারি সার্চের কাজ করার প্রক্রিয়া:
- প্রথমে তালিকার মাঝের উপাদান চিহ্নিত করুন।
- যদি মাঝের উপাদানের মান লক্ষ্য মানের সমান হয়, তাহলে ইনডেক্স ফেরত দিন।
- যদি লক্ষ্য মান ছোট হয়, তাহলে বাম অর্ধেকের উপাদানগুলির জন্য পুনরাবৃত্তি করুন।
- যদি লক্ষ্য মান বড় হয়, তাহলে ডান অর্ধেকের উপাদানগুলির জন্য পুনরাবৃত্তি করুন।
- যদি তালিকার শেষ হয়ে যায় এবং লক্ষ্য মান পাওয়া না যায়, তাহলে "নেই" ফেরত দিন।
উদাহরণ (Python):
def binary_search(arr, target):
left, right = 0, len(arr) - 1 # তালিকার সূচক নির্ধারণ
while left <= right:
mid = (left + right) // 2 # মাঝের সূচক নির্ধারণ
if arr[mid] == target:
return mid # লক্ষ্য মানের ইনডেক্স ফেরত
elif arr[mid] < target:
left = mid + 1 # ডান অর্ধেক পরীক্ষা
else:
right = mid - 1 # বাম অর্ধেক পরীক্ষা
return -1 # লক্ষ্য মান না পেলে -1 ফেরত
# ব্যবহার উদাহরণ
arr = [1, 2, 3, 4, 5] # সাজানো তালিকা
target = 3
result = binary_search(arr, target)
print(result) # আউটপুট: 2
উপসংহার
সার্চিং অ্যালগরিদমগুলি ডেটা খুঁজে বের করার জন্য গুরুত্বপূর্ণ। লিনিয়ার সার্চ সরল এবং আনঅর্ডারড তালিকার জন্য কার্যকর, তবে এর টাইম কমপ্লেক্সিটি O(n)। অপরদিকে, বাইনারি সার্চ একটি দ্রুত অ্যালগরিদম যা O(log n) টাইম কমপ্লেক্সিটিতে কাজ করে, তবে এটি শুধুমাত্র সাজানো তালিকার জন্য কার্যকর। আপনার ডেটার ধরন এবং প্রয়োজন অনুসারে সঠিক সার্চিং অ্যালগরিদম নির্বাচন করা জরুরি।
Read more
